#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=5e4+10;
int A,p,n,mp[MAXN],tot;
struct node
{
	int x,y,z,ans;
}a[MAXN];
inline bool cmp1(node a,node b)
{
	return a.x==b.x?(a.y==b.y?a.z<b.z:a.y<b.y):a.x<b.x;
}
inline bool cmp2(node a,node b)
{
	return a.y==b.y?a.z<b.z:a.y<b.y;
}
struct BIT
{
	int num[MAXN];
	inline int lowbit(int x)
	{
		return x&-x;
	}
	void update(int o,int x)
	{
		while(o<=n)
		{
			num[o]=max(num[o],x);
			o+=lowbit(o);
		}
		return;
	}
	int query(int o)
	{
		int ret=0;
		while(o)
		{
			ret=max(ret,num[o]);
			o-=lowbit(o);
		}
		return ret;
	}
	void clear(int o)
	{
		while(o<=n)
		{
			if(!num[o])break;
			num[o]=0;
			o+=lowbit(o);
		}
		return;
	}
}T1;
void CDQ(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	sort(a+l,a+1+mid,cmp2);
	sort(a+mid+1,a+r+1,cmp2);
	int i=l,j=mid+1;
	while(i<=mid||j<=r)
	{
		if(j>r||(i<=mid&&a[i].x<a[j].x&&a[i].y<a[j].y))T1.update(a[i].z,a[i].ans),++i;
		else a[j].ans=max(a[j].ans,T1.query(a[j].z-1)+1),++j;
	}
	for(int i=l;i<=mid;++i)T1.clear(a[i].z);
	sort(a+l,a+r+1,cmp1);
	CDQ(mid+1,r);
	return;
}
int main()
{
	A=read();p=read();n=read();
	LL t=1;
	for(int i=1;i<=n;++i)
	{
		a[i].x=(t=t*A%p);
		a[i].y=(t=t*A%p);
		a[i].z=(t=t*A%p);
		if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
		if(a[i].x>a[i].z)swap(a[i].x,a[i].z);
		if(a[i].y>a[i].z)swap(a[i].y,a[i].z);
		a[i].ans=1;
		mp[i]=a[i].z;
	}
	sort(mp+1,mp+1+n);
	tot=unique(mp+1,mp+1+n)-mp-1;
	for(int i=1;i<=n;++i)a[i].z=lower_bound(mp+1,mp+1+tot,a[i].z)-mp;
	sort(a+1,a+1+n,cmp1);
	CDQ(1,n);
	int ans=0;
	for(int i=1;i<=n;++i)ans=max(ans,a[i].ans);
	printf("%d\n",ans);
	return 0;
}
